Wireless communication among electronic devices has been increasing as the benefits and conveniences of wireless communication become more preferred. A wireless communication system or wireless network is often described as containing nodes (or more precisely, circuitry associated with the concept of a node) and a wireless medium (WM) over which the nodes' circuitry communicate to convey information. Where some action or activity is described as happening at (or being done at) a node, it should be understood that the electronic device and/or network interface that is at (or simply is) the node is the circuitry that is performing the action or activity. For example, sending data from node A to node B means transmitting a signal from circuitry associated with node A and receiving that signal (or more precisely, the transmitted signal modified by the medium) using circuitry associated with node B.
The information conveyed between nodes can be digital data and digitized analog signals, or other forms of information, but communication system design often assumes that digital data is being conveyed and higher network layers interpret the data appropriately. For purposes herein, it is assumed that data exists at one node, is provided to lower network layers, is conveyed to another node over a WM, is received by another node correctly or incorrectly and then is conveyed to upper network layers at the receiver. In one model, two networked devices run applications that pass data between themselves by having the sending device's application convey data to an application layer of a network stack, which conveys data to lower levels, ultimately to a medium access control (MAC) layer and a physical network (PHY) layer, and the process is inverted at the recipient.
To set up a wireless network, all that is needed is a plurality of electronic “node” devices capable of transmitting and receiving data in a manner understood by the two (or more) nodes involved in a conversation, with the node devices appropriately placed such that they can communicate in the medium that exists between the devices. The medium could be some type of dielectric material, but more commonly, the medium is the air space and objects (walls, chairs, books, glass. etc.) that are between devices or are positioned such that they have an effect on the signals transmitted between devices. Presumably, the node devices are assigned unique identifiers to distinguish transmissions, but this might not always be necessary. Examples of such unique identifiers are MAC addresses and IP addresses.
As the existence of various wireless media and their properties are known and are not the focus of this disclosure, the medium is often just shown in the attached figures as a cloud. Thus, it should be understood that supplier of a set of two or more powered devices that can communicate supplies a wireless network; the wireless medium is presumed.
Wireless communication systems can be categorized based on coverage range, which in some cases is dictated by use. A wireless local area network or “WLAN”, has a typical coverage range on the order of 300 feet and is useful for providing communications between computing devices in some (possibly loosely) defined space such as a home, office, building, park, airport, etc. In some modes of operation, one or more of the nodes is coupled to a wired network to allow other nodes to communicate beyond the wireless network range via that wired network. In 802.11 terminology, such nodes are referred to as “access points” and the typical protocol is such that the other nodes (referred to as “stations”) associate with an access point and communication is generally between a station and an access point. Some wireless networks operate in an “ad hoc” mode, wherein node devices communicate with each other without an access point being present.
A personal area network or “PAN” is a short-range wireless network, with typical coverage ranges on the order of 30 feet, usable to connect peripherals to devices in close proximity, thereby eliminating cables usually present for such connections. For example, a PAN might be used to connect a headset to a mobile phone or music/audio player, a mouse or keyboard to a laptop, a PDA or laptop to a mobile phone (for syncing, phone number lookup or the like), etc. Yet another example of a wireless PAN application is wireless medical monitoring devices that wirelessly connect monitoring hardware to a pager or similar read-out device. Yet another example is a remote control that connects to a wireless-enabled electronic device.
Some networks might fall in a gray area between a WLAN and a PAN, but in many cases, a network is clearly one or the other. A personal area network (PAN) is generally used for the interconnection of information technology devices within the range of an individual person, typically within a range of 10 meters. For example, a person traveling with a laptop will likely be the sole user of that laptop and will be the same person handling the personal digital assistant (PDA) and portable printer that interconnect to the laptop without having to plug anything in, using some form of wireless technology. Typically, PAN nodes interact wirelessly, but nothing herein would preclude having some wired nodes. By contrast, a wireless LAN tends to be a local area network (LAN) that is connected without wires and serves multiple users.
Equipment connecting to a wireless communication system in general, and to a wireless PAN communication system in particular, is typically used for applications where power usage, weight, cost and user convenience are very important. For example, with laptops, low-cost accessories are preferable, and it is critical that the power usage of such accessories be minimized to minimize the frequency at which batteries need to be replaced or recharged. The latter is a burden and annoyance to the user and can significantly reduce the seamless user experience.
Weight and complexity are additional concerns in many wireless communication systems. Particularly with mobile devices such as laptops, weight is a concern and the user would rather not have to deal with the hassle of carrying around a multiplicity of devices. Mobile devices are devices that can be expected to be in use while moving, while portable devices are devices that are movable from place to place but generally are not moving when in use. The considerations for mobile devices also apply to portable devices, albeit sometimes with less of a concern. For example, with a wireless connection of a peripheral to a laptop, both devices are likely to be used while mobile or moved frequently and carried around. Thus, weight and the number of devices is an important consideration. With portable devices, such as a small desktop computer with a wireless trackball, as long as the total weight is below a user's carrying limit, the weight is not as much a concern. However, battery life is often as much a concern with portable devices as it is with mobile devices.
There are shades of grey between “portable” and “mobile” and it should be understood that the concerns of mobile applications and portable applications can be considered similar, except where indicated. In other words, a mobile device can be a portable device in the examples described herein.
Where a computing and/or communication device connects to a WLAN, it uses wireless circuitry that often times are already built into the computing device. If the circuitry is not built in, a WLAN card (such as a network interface card, or “NIC”) might be used. Either way, some antenna circuitry is used and power is required to run that circuitry.
Where a device also connects wirelessly to peripherals or other devices over short links often referred to as forming a “personal area network” or “PAN”, circuitry is needed for that connection as well. This circuitry is typically provided with an external interface unit that is plugged into or onto the device. For example, where the device is a laptop, the circuitry might be provided by a Universal Serial Bus (USB) dongle that attaches to a USB port of the laptop. The USB dongle contains the radio circuitry needed to communicate wirelessly over the short wireless links.
In general, a wireless connection between two or more devices requires that each device include wireless network circuitry for conveying signals over the medium and receiving signals over the medium, as well as processing/communication circuitry to receive, process and/or convey data and/or signals to that wireless network circuitry. The processing/communication circuitry could be implemented with actual circuits, software instructions executable by a processor, or some combination thereof. In some variations, the wireless network circuitry and processing/communication circuitry are integrated (such as with some PDAs, wireless mice, etc.) or are separate elements (such as a laptop as the processing/communication circuitry and a network PCMCIA card as the wireless network circuitry).
For ease of understanding this disclosure, where it is important to make the distinction between devices, a device that exists to provide wireless connectivity is referred to as a “network interface”, “network interface device”, “wireless network interface device” or the like, while the device for which the wireless connectivity is being provided is referred to as a “computing device” or an “electronic device” notwithstanding the fact that some such devices do more than just compute or might not be thought of as devices that do actual computing and further notwithstanding the fact that some network interface devices themselves have electronics and do computing. Some electronic devices compute and communicate via an attached network interface device while other electronic devices might have their network interface devices integrated in a non-detachable form. Where an electronic device is coupled to a wireless network interface to a wireless network, it is said that the device is a node in the network and thus that device is a “node device”.
An 802.11x (x=a, b, g, n, etc.) NEC (network interface card) or 802.11x built-in circuitry might be used for networking an electronic device to the outside world, or at least to devices at other nodes of a WLAN 802.11x network, while using an external dongle or a similar interface device with Bluetooth or proprietary wireless circuitry for communication between the computing device and the peripheral or other PAN node.
A device that is equipped with an 802.11x-conformant network interface to the WM is herein referred to as a station or “STA”. In 802.11 terminology, set of STAs constitutes a Basic Service Set (“BSS”). A set of STAs that communicate in a peer-to-peer configuration is referred to as an “802.11x ad-hoc” network or an independent BSS (MSS). A set of STAs controlled by a single coordinator is referred to as an 802.11x infrastructure network. The coordinator of a BSS is herein referred to as the access point or “AP”.
A typical access point device is wired to a wired network and is also wired to an external source of electricity, such as being plugged into a wall socket or wired to a building's power grid. For example, a building, an airport or other space people might occupy might have fixed access points mounted throughout the space to provide adequate network coverage for the purpose of providing access to the Internet or other network for the people occupying the space, via their portable or mobile devices. As such, access points are typically always on so that the wireless network is available whenever suitable portable or mobile devices are carried into the space.
The use of different technologies for WLAN and wireless PAN connectivity increases cost, weight and power usage (at the COORD side and/or the PER side), and impairs a seamless user experience. Those disadvantages could be resolved by equipping the peripheral or PAN nodes with 802.11x wireless circuitry, thus eliminating the dedicated PAN technologies altogether. However, PAN nodes are often very power-sensitive devices. They usually are battery-operated devices and their small form factor prohibits the use of bulky batteries with large capacity. Instead, small batteries with limited power capacity are used. Such peripherals cannot typically support the power usage requirements typical of WLAN wireless circuitry, such as 802.11x circuitry. A host of other difficulties are present in view of the optimizations, goals and designs of differing network protocols.
Another drawback is that independent LANs and PANs may interfere if they share a common frequency band.
Many communications systems have multiple devices that might use a communications medium wherein the medium can only support transmissions from less than all of the devices simultaneously. For example, where the medium is wireless frequency spectrum within a given spatial volume, perhaps only one or a few devices can transmit using that wireless frequency spectrum in that spatial volume at one time. To avoid situations where transmissions are interfering, such communication systems typically have a protocol for coordinating use of the medium by the multiple devices.
Coordination could be by preassignment, wherein each device is allocated a time slice and only transmits (if at all) during its assigned time slice. This wastes valuable bandwidth unless all of the devices have data to transmit during their assigned time slice. Coordination could also be done by contention and reservation, as is common in network protocols, such as the Ethernet protocol for wired networks, 802.11 for wireless networks, etc.
With contention and reservation, a device that wishes to transmit first listens to the wireless medium for activity. If there is no activity, it signals an intent to reserve the medium. If the reservation succeeds, such as when a reservation message is sent before any other device sends an interfering transmission, the other devices using the medium would defer for a reservation period before they attempt to transmit data (typically such transmission is in turn preceded by that device's reservation of the medium).
Special problems arise where the devices that need to reserve the medium are low-power devices that might not transmit with high enough power that other devices will detect and those devices might transmit and swamp the low-power device's transmission. To deal with such cases, a coordinator for the network might handle requests for reservation. For example, where the coordinator is operated by the device that uses the other devices on the network, the coordinator C might send out a signal indicating a reservation for another device D and include a reservation time sufficient for device D to transmit the data requested by coordinator C.
A medium reservation for communication between two or more devices might be for a regular or one-time communication sequence between the devices. In many systems, reservations are made for streaming media data types or other constant-rate or near-constant-rate communications (hereafter called “streaming communications”). Examples include RSVP (Reservation Protocol) over Ethernet and the Isochronous data transfer type over Universal Serial Bus (USB), defined herein as USB 1.0, 1.1, 2.0, Wireless USB, and further enhancements and derivatives of USB. In other systems, a reservation mechanism is part of a collision-avoidance scheme, but is not specifically designed for streaming communications. In yet other cases, the reservation mechanism could exist for different reasons.
The present invention relates to electronic devices that contend among themselves for use of a medium in general and more particularly to electronic devices that reserve the medium and defer to the reservations of others using the medium.
A common medium reservation system used in many communications systems is a message exchange comprising a Ready-To-Send (RTS) message from one device and Clear-To-Send (CTS) message from a second device. The RTS message from the first device indicates a desire for the first device to transmit; CTS from the second device indicates that the first device may now transmit. A specific example of a communication system with this medium reservation scheme is an 802.11-compatible Wireless Local Area Network (WLAN), though this and similar schemes are used in other communications systems.
In some systems with a medium reservation mechanism, the reservation mechanism is asymmetric, i.e., one device (known as the “master”) makes a reservation for communication initiated from another device (known as the “slave”), but the slave device does not make reservations for the master device. The reason for the slave device relying on the master device for reservations may vary. For example, where the slave device lacks some or all of the information about other devices to be able to make a correct or fair decision about when to transmit, the slave device would allow the master device to reserve the medium on its behalf. As another example, the slave device may not have a communication path to all other devices sharing the communications channel. As yet another example, the slave device may be a simple device without the capability required to make such a decision. For any combination of these reasons and/or other reasons, the system is set up such that the master device makes reservations for the slave device.
As used herein, unless otherwise indicated, a master device is a device in the communication system responsible for the reservation scheduling for a particular transaction between two devices and the slave device is a device involved in the transaction but not responsible for the scheduling. “Master” and “slave” are designations for a particular one-way communication. It is possible for a device to be a master device for communications with one device and a slave in its communications with another device. It is also possible for a device to be a master device for transmitting to a device, and a slave device for receiving from that same device. Further, which device is master device and which is slave device may be a static designation or may change between communication sessions or even during a communication session. Such a change may be negotiated according to a communication standard or may be outside the scope of the communications standard.
In a system with a medium reservation mechanism, a service interval (SI) is defined herein as the interval between the start of two successive service periods (SPs). A service period (SP) is defined herein as a contiguous time during which one or more attempts is made to communicate one or more messages from a master device to a slave device and/or a slave device to a master. In general, it is expected that during an SP, both devices are attempting to communicate with each other by either transmitting a packet or listening for a packet to be transmitted by the other device. It is possible that there are small inactivity times in between packet exchanges, but such inactivity times are typically significantly shorter than the SI. The service interval may be a constant value or can be irregular from service period to service period. A service period may always be a fixed length or may vary from service period to service period. As an example, a master device and a slave device may agree on timing such that they can power down some or all of their circuitry in between SPs. In such cases, the master and slave device preferably time their power up process such that the necessary circuits are operational at, or slightly prior to, the start of an SP.
The mechanism whereby a master device reserves the medium for a slave device works well when a master device knows, at the start of a service period, the amount of data a slave device will transmit during that service period. In that case, a master device makes the reservation for the time period needed for the amount of data the slave device has ready and the slave device transmits the data when its reserved time slot occurs.
However, in many applications, a master does not know the amount of data a slave device has to transmit in a given service period, so it is possible that a master device will not create a reservation long enough in a particular service period for a slave device to complete its communication in that same service period, or conversely that the master device may create an excessively long medium reservation for the slave's communication which the slave cannot make use of and unnecessarily takes up medium capacity.
A variable-bit-rate (VBR) stream is defined as any communication in which the amount of data per unit time is not constant. This can be a variable-bit-rate media stream, a constant-bit-rate (CBR) stream plus a variable data component, or any other data stream where the amount of data per service period is not known by the receiving system. A VBR stream therefore obviously poses problems for a master device attempting to make a correct medium reservation for a stream coming from a slave.
In contrast to a VBR stream, a constant-bit-rate (CBR) stream presents the same number of bits per unit of time or per some other known unit. In an ideal system, the master could predict exactly the number of bits that the slave device would like to transmit based on the time or distance since the last service period. The master could therefore always make the correct reservation for the slave's transmission.
However, in many cases a stream that is nominally a CBR stream still does not make it possible for the master device to always make the correct reservation. There could be a number of reasons why a medium reservation might be incorrect, even in a CBR application. For example, if data was lost during an earlier service period that the slave device wishes to retry in addition to the other data that should be transmitted in this service period, or the slave device has additional data to transmit in this service period in addition to the usual CBR data. Other reasons might include that there is uncertainty in the time at which the slave's transmit opportunity begins which has not been accounted for in the length of the medium reservation. This can occur, for example, in a system where the start of the slave's transmit opportunity is based on a message from the master device that could get delayed due to routing delays or contention access mechanisms. This can also occur due to other reasons.
Yet other reasons include where the master device and slave device are operating off independent or loosely-synchronized clocks that have drifted since the last communication, causing the two to make a different calculation of the amount of data to be transmitted in this service period, or if the master device's calculation is based on an expectation of the data rate of the master device and/or slave device communication, and the master device and/or slave device use a different data rate for the transmission. This could happen, for example, if the reservation is in units of time instead of units of bits or bytes, and the master device and/or slave device transmit at a different bit rate than the master device anticipated in its calculation.
One example of a medium reservation system is defined by the Enhanced Wireless Consortium (EWC), which has a proposal pending to the IEEE 802.11(n) task group. See, for example, “Interoperability MAC Specification v1.0” published by the EWC (hereinafter the “EWC specification”). The proposal defines a mechanism for using a CTS-to-self, an RTS-CTS exchange, or other packet sequence with an extended reservation (called a “long NAV”) to protect multiple packets within the transmission opportunity (TXOP). The concept of an asymmetric reservation is included in this EWC specification as well, where a reservation is made with a poll from a master device (called the Hybrid Controller (HC)), and responded to by a slave device.
A limitation of the technique in the EWC specification is that it does not provide a mechanism for a slave device to request a reservation extension. In order to support an uncertain amount of data delivery in a service interval, the master device needs to over-allocate the medium then have the slave device use a specific packet (a “CF-End” packet, for example) to indicate the end of its transmission. This is undesirable because, in many applications, the slave device only occasionally needs extra medium capacity in a service period. In such cases, the master device would have over-allocated the medium many times for these occasional extra transmissions. Furthermore, other devices may have turned off their receivers after hearing the long NAV message from the master and will still be disabled at the time when a CF-End packet indicates the early end of the period. Those devices that had their receivers disabled would then not be able to take advantage of the freed-up medium.
The technique for medium contraction in the EWC specification also has an important limitation. A medium contraction is signaled in the EWC specification using the CF-End packet at the end of a device's transmission. It is not ideal to wait to signal a medium contraction until the end of a transmission because (1) it does not give other devices that may want to use the medium any time to prepare a new transmission before the transmission has ended, (2) other devices may have turned off their receivers while waiting until the end of the previous reservation, and therefore will not know about the newly-available medium, and (3) the transmission of a CF-end packet takes up additional network capacity, making it an unattractive technique especially in applications where the nominal medium reservation requirements are known and deviations from this nominal medium reservation requirement only occur occasionally.
In light of the above, improved medium reservation protocols, methods and apparatus are proposed.